package demo.hw;

public class _猴子爬山 {
    public static void main(String[] args) {
        /**
         * 猴想去从山脚爬到山顶，途中经过一个有个N个台阶的阶梯，但是这猴子有一个习惯：
         * 每一次只能跳1步或跳3步，试问猴子通过这个阶梯有多少种不同的囚跳跃方式？
         * 输入描述
         * 输入只有一个整数N(0<N<=50)此阶梯有多少个台阶。
         * 输出描述
         *
         * 输入
         * 50
         * 输出
         * 122106097
         * 输入
         * 3
         * 输出
         * 3
         */
        /**
         * 动态规划
         * 思路dp[i]=dp[i-1]+dp[i-3]
         *
         * 初始条件
         * dp[0] = 1（表示地面，有一种方式“不跳”）
         * dp[1] = 1（只能从地面跳1步）
         * dp[2] = 1（只能1+1）
         * dp[3] = 2（1+1+1 或 3）
         *
         */
        int k = 50;
        int[] dp = new int[k + 1];
        dp[0] = 1;
        dp[1] = 1;
        if (k >= 2) dp[2] = 1;
        if (k >= 3) dp[3] = 2;
        for (int i = 4; i <= k; i++) {
            dp[i] = dp[i - 1] + dp[i - 3];
        }
        System.out.println(dp[k]);
    }
}
